package com.算法.递归_查找_排序;

public class 什么是递归 {
    static void test(int i){
        //一个方法里调用自己的方法，就叫递归（一般有参数，调用时参数-1，无参无需-1）
        test(i-1);
    }

    public static void main(String[] args) {
        int a = test1(5);
        System.out.println("k的阶乘=> "+a);
        test2(1,9);
        int sum = test3(new int[]{1,2,3,4,5},0);
        System.out.println("数组的和为："+sum);
        System.out.println("abcd的翻转为："+reverse("abcd",3));
        System.out.println("斐波那契数列第n项:=>"+test5(9));
        System.out.println("最小公约数："+gcd(10,4));


    }
    //求数(k)的阶乘
    /*
    * 找重复：K*(k-1)的阶乘,求n- 1的阶乘是原问题的重复(规模更小)---子问题
    * 找变化：变化的量应该作为参数
    * 找边界：出口；
    * */
    public static int test1(int k) {
        if(k==1){
            return 1;
        }
        return k * test1(k-1);
    }
    //打印i-j
    public static void test2(int a,int b){
        if(a>b){
            return;
        }
        System.out.println(a);
        test2(a+1,b);
    }
    //数组求和
    static int test3(int[] arr , int begin){
        if(begin == arr.length-1){
            return arr[begin];
        }
        return arr[begin]+test3(arr,begin+1);
    }

    //  翻转字符串,例如：abcd--》dcba
    //从后面的d开始
    static String reverse(String src ,int end){
        if(end == 0){
            return ""+src.charAt(0);
        }
        return src.charAt(end)+reverse(src,end-1);
    }

    //求斐波那契数列第n项的数 ，1，1，2，3，5，8，13，21...
    //第2项=前两项的和===》f(n)=f(n-1)+f(n-2)
    static int test5(int N){
        if(N==1 || N==2) {
            return 1;
        }
        return test5(N-1)+test5(N-2);
    }

    //最大公约数
    static int gcd(int a,int b){
        if(b==0){
            return a;
        }
        return gcd(b,a%b);
    }
    //插入排序改递归
    static void insertSort(int[] arr,int k){
        if(k==0){
            return;
        }
        insertSort(arr,k-1);
        int x = arr[k-1];
        int index = k-1;
        while(index>-1 && x< arr[index]){
            arr[index+1] = arr[index];
            index--;
        }
        arr[index+1] = x;
    }
}
